package BF_DP;

public class Test {
    public static int min1(int[] arr ,int aim){
        return f(arr,0,aim);
    }
    /*
    暴力尝试的过程:完全没有优化
    arr[index] 组成出rest 这么多的钱, 最少的硬币数量返回*/
    public static int f(int[] arr , int index,int rest){
        if (rest < 0)return -1;
        if (rest == 0)return 0;
        //rest > 0
        if (index == arr.length)return -1;
        //rest >0 并且有硬币:俩种选择:1不要当前的硬币, 2选择当前的硬币
        int p1 =f(arr,index+1,rest);
        int p2 = f(arr,index+1,rest-arr[index]);
        if (p1 == -1 && p2 == -1){//当这个选择的数已经超过了rest,那么后续的所有组合都是错的
            return -1;
        }else {
            if (p1 == -1){
                return p2+1;
            }
            if (p2 == -1){
                return p1;
            }
            return Math.min(p1,p2+1);
        }
    }
    /*优化思路:做一个二维表
    * 记忆化搜索的方法*/
    public static int min2(int[] arr ,int aim){
        int[][] dp = new int[arr.length][aim+1];
        //初始化 :  -2 表示没算过,-1表示无效解
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = -2;
            }
        }
        return f2(arr,0,aim,dp);
    }

    public static int f2(int[] arr , int index,int rest,int[][] dp){
        //dp表没办法表示负数的情况
        if (rest < 0)return -1;
        if (dp[index][rest] != -2){
            return dp[index][rest];
        }
        if (rest == 0){
            dp[index][rest] = 0;
        }else if (index == arr.length){
            dp[index][rest] = -1;
        }else {
            int p1 = f2(arr,index+1,rest,dp);
            int p2 = f2(arr, index+1, rest-arr[index], dp);
            if (p1 == -1 && p2 == -1){//当这个选择的数已经超过了rest,那么后续的所有组合都是错的
                dp[index][rest] = -1;
            }else {
                if (p1 == -1){
                    dp[index][rest] = p2+1;
                }
                if (p2 == -1){
                    dp[index][rest] = p1;
                }
                dp[index][rest] = Math.min(p1,p2+1);
            }
        }
     return dp[index][rest];
    }
    /*动态规划的优化 : 递归函数怎么写,动态规划怎么调
    * 将递归函数的调用,变成dp表的调用*/
    public static int min3(int[] arr ,int aim){
        int N=arr.length;
        int[][] dp = new int[N+1][aim+1];
        for (int row = 0; row <= N;row++){
            dp[row][0] = 0;
        }
        for (int col = 1; col <= N; col++) {
            dp[col][0] = -1;
        }
        for (int index = N-1; index >= 0; index--) {
            for (int rest = 1; rest <= aim; rest++) {
                //rest >0 并且有硬币:俩种选择:1不要当前的硬币, 2选择当前的硬币
                int p1 =dp[index+1][rest];
                int p2 = -1;
                // p2 防止越界
                if (dp[index+1][rest-arr[index]] >= 0){
                    p2 = dp[index+1][rest-arr[index]];
                }
                if (p1 == -1 && p2 == -1){//当这个选择的数已经超过了rest,那么后续的所有组合都是错的
                    dp[index][rest] = -1;
                }else {
                    if (p1 == -1){
                        dp[index][rest] = p2+1;
                    }
                    if (p2 == -1){
                        dp[index][rest] = p1;
                    }
                    dp[index][rest] = Math.min(p1,p2+1);
                }
            }
        }
        return dp[0][aim];
    }


/****************************************求一个目的硬币的值:能有多少种方法**************************************************************************/
    /*
    arr:硬币的面值
    aim:最终要达成的目标,固定参数
    index : 如果自由选择 arr[index ] 但是之前的硬币已经让你有了pre这么多的钱
    这个f是返回方法数*/
    public static int fanfa(int[] arr ,int index,int pre,int aim){
        if (index == arr.length){
            return pre == aim?1:0;
        }
        return fanfa(arr,index+1,pre,aim)+fanfa(arr, index+1, pre+arr[index], aim);
    }
}
